Updated at 2021.4.27

Fast Fourier Transform

이 글을 수학으로 배우는 파동의 법칙 이라는 책을 읽고 정리하였다. 이전 글에서 유도한 푸리에 변환 공식은 다음과 같다.

\begin{align}G(f) = \int_{-\infty}^{\infty}{f(t)e^{-i 2\pi f t} dt}\end{align}

위 식을 이용하여 실제 음성의 파동을 푸리에 변환하기 위해서는 적분을 무한대로 구간에서 해야 하는데, 현실에서는 그렇게 할 수 없다. 일정 시간 간격으로 유한개의 파동값을 읽어서 사용할 수 밖에 없다.

불연속 푸리에 변환

그 일정 시간 간격을 \(\tau\) 라고 하고, 읽어낸 값의 개수를 \(N\) 이라고 하면, 위의 적분식은 주파수 \(f= \frac{n}{\tau N}\) 일때, 위의 수식은 아래와 같이 쓸 수 있다.

\begin{align}\red{G(\frac{n}{\tau N}) = \sum_{k=0}^{N-1} \lbrace\tau \cdot f(k\tau) e^{-i 2\pi k \frac{n}{\tau N}} \rbrace}\end{align}

위 식을 불연속 푸리에 변환이라고 한다. 위의 식의 문제점은 관찰 구간내에서 최대 \(N/2\) 회 진동하는 파동까지만 계산할 수 있다. (참고로, \(M\) 번 진동하는 파동은 최소 \(2M\) 개의 값을 읽어야 식별 가능 하기 때문임)

예를 들어 0.3초짜리 4000Hz의 음성에서 푸리에 계수 1개를 뽑아내기 위해서는 2400회의 계산이 필요하고

\begin{align}\tau = \frac{0.5}{4000} = 1.25e^{-4}\end{align}

\begin{align}N = \frac{0.3}{\tau} = 2400\end{align}

푸리에 계수를 1Hz부터 4000Hz까지 4000개를 계산하려면, \(2400\times 4000\) 회의 지수함수 및 곱셈 계산이 필요하다.

계산 횟수 줄이기

설명의 편의를 위해 위의 식에서 \(\tau = 1\) 라고 하면,

\begin{align}\red{G(n/N) = \sum_{k=0}^{N-1} f(k) W^{nk}}\end{align}

여기서,

\begin{align}W = e^{ -\frac{i 2\pi}{N}}\end{align}

추가로, \(N = 8\) 라고 하면,

\begin{align}G(n/8) = \sum_{k=0}^{7} f(k) W^{nk}\end{align}

\begin{align}W = e^{ -\frac{i 2\pi}{8}}\end{align}

\(W\) 는 회전 연산자라고 할 수 있는데, \(N= 8\) 일 때는 \(n\) 이 임의의 정수이고, \(0 \le k \lt 8\) 에 대해서 아래와 같음을 알 수 있다.

\begin{align}W^{k + 8n} = W^{k}\end{align}

따라서

\begin{align}\begin{split}G(n/8) &= \sum_{k=0}^{N-1} f(k) W^{nk}\\ &=\sum_{k=0}^{\frac{N}{2}-1} f(2k) W^{n2k} + \sum_{k=0}^{\frac{N}{2}-1} f(2k+1) W^{n(2k+1)}\end{split}\end{align}

추가로 정리하면,

\begin{align}\red{G(n/8) =\sum_{k=0}^{\frac{N}{2}-1} p(k) W^{2nk} + W^n \cdot \sum_{k=0}^{\frac{N}{2}-1} q(k) W^{2nk}}\end{align}

여기서 \(p(k) = f(2k)\), \(q(k) = f(2k+1)\) 이다. 위 식의 장점은 \(G(\frac{4+m}{8})\) 를 계산하고자 할 때 \(G(\frac{m}{8})\) 을 계산할 때 사용한 값을 그대로 사용할 수 있다는 것이다.

즉 64번의 계산량이 짝수일 때 16번, 홀수 일때 16번 + 4번(\(W^n\) 을 곱하는 회수)로 총 34번으로 줄어든다.

유사한 절차를 한번 더 진행하면,

\begin{align}\begin{split}G(n/8) &= \sum_{k=0}^{\frac{N}{4}-1} a(k) W'^{2nk} + W'^n \cdot \sum_{k=0}^{\frac{N}{4}-1} b(k) W'^{2nk}\\ &+ W^n \Big( \sum_{k=0}^{\frac{N}{4}-1} c(k) W'^{2nk} + W'^n \cdot \sum_{k=0}^{\frac{N}{4}-1} d(k) W'^{2nk}\Big) \end{split}\end{align}

여기서 \(a(k) = p(2k)\), \(b(k) = p(2k+1)\), \(c(k) = q(2k)\), \(d(k) = q(2k+1)\), \(W' = W^2\) 이다.

계산회수는 16번에, \(W^n\) 곱하기 회수 4번, \(W'^n\) 곱하기 회수 4번으로 총 24회로 줄어든다.

위와 같은 알고리즘을 활용하여, \(N=8\) 일때는 \(2^3\) 으로 2번의 절차를 통해 회수를 줄였는데, 일반적으로 \(N=1024 = 2^{10}\) 개의 점을 취하면, 9번의 절차를 통해 계산 회수를 획기적으로 줄일 수 있다.

이 알고리즘을 FFT (Fast Fourier Transform) 이라고 한다.

Most Popular #3

Recent #3